<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>FDLA and FMMC solutions for a 64-node, 95-edge cut-grid graph</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/graph_laplacian/html/cut_grid_example.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>FDLA and FMMC solutions for a 64-node, 95-edge cut-grid graph</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% S. Boyd, et. al., "Convex Optimization of Graph Laplacian Eigenvalues"</span>
<span class="comment">% ICM'06 talk examples (www.stanford.edu/~boyd/cvx_opt_graph_lapl_eigs.html)</span>
<span class="comment">% Written for CVX by Almir Mutapcic 08/29/06</span>
<span class="comment">% (figures are generated)</span>
<span class="comment">%</span>
<span class="comment">% In this example we consider a graph described by the incidence matrix A.</span>
<span class="comment">% Each edge has a weight W_i, and we optimize various functions of the</span>
<span class="comment">% edge weights as described in the referenced paper; in particular,</span>
<span class="comment">%</span>
<span class="comment">% - the fastest distributed linear averaging (FDLA) problem (fdla.m)</span>
<span class="comment">% - the fastest mixing Markov chain (FMMC) problem (fmmc.m)</span>
<span class="comment">%</span>
<span class="comment">% Then we compare these solutions to the heuristics listed below:</span>
<span class="comment">%</span>
<span class="comment">% - maximum-degree heuristic (max_deg.m)</span>
<span class="comment">% - constant weights that yield fastest averaging (best_const.m)</span>
<span class="comment">% - Metropolis-Hastings heuristic (mh.m)</span>

<span class="comment">% generate a cut-grid graph example</span>
[A,xy] = cut_grid_data;

<span class="comment">% Compute edge weights: some optimal, some based on heuristics</span>
[n,m] = size(A);

[ w_fdla, rho_fdla ] = fdla(A);
[ w_fmmc, rho_fmmc ] = fmmc(A);
[ w_md,   rho_md   ] = max_deg(A);
[ w_bc,   rho_bc   ] = best_const(A);
[ w_mh,   rho_mh   ] = mh(A);

tau_fdla = 1/log(1/rho_fdla);
tau_fmmc = 1/log(1/rho_fmmc);
tau_md   = 1/log(1/rho_md);
tau_bc   = 1/log(1/rho_bc);
tau_mh   = 1/log(1/rho_mh);

fprintf(1,<span class="string">'\nResults:\n'</span>);
fprintf(1,<span class="string">'FDLA weights:\t\t rho = %5.4f \t tau = %5.4f\n'</span>,rho_fdla,tau_fdla);
fprintf(1,<span class="string">'FMMC weights:\t\t rho = %5.4f \t tau = %5.4f\n'</span>,rho_fmmc,tau_fmmc);
fprintf(1,<span class="string">'M-H weights:\t\t rho = %5.4f \t tau = %5.4f\n'</span>,rho_mh,tau_mh);
fprintf(1,<span class="string">'MAX_DEG weights:\t rho = %5.4f \t tau = %5.4f\n'</span>,rho_md,tau_md);
fprintf(1,<span class="string">'BEST_CONST weights:\t rho = %5.4f \t tau = %5.4f\n'</span>,rho_bc,tau_bc);

<span class="comment">% plot results</span>
figure(1), clf
plotgraph(A,xy,w_fdla);
text(0.425,1.05,<span class="string">'FDLA optimal weights'</span>)

figure(2), clf
plotgraph(A,xy,w_fmmc);
text(0.425,1.05,<span class="string">'FMMC optimal weights'</span>)

figure(3), clf
plotgraph(A,xy,w_md);
text(0.375,1.05,<span class="string">'Max degree optimal weights'</span>)

figure(4), clf
plotgraph(A,xy,w_bc);
text(0.375,1.05,<span class="string">'Best constant optimal weights'</span>)

figure(5), clf
plotgraph(A,xy,w_mh);
text(0.3,1.05,<span class="string">'Metropolis-Hastings optimal weights'</span>)
</pre>
<a id="output"></a>
<pre class="codeoutput">
Warning: A non-empty cvx problem already exists in this scope.
   It is being overwritten. 
 
Calling sedumi: 4166 variables, 4070 equality constraints
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
Split 6 free variables
eqs m = 4070, order n = 141, dim = 8205, blocks = 3
nnz(A) = 4765 + 0, nnz(ADA) = 8900020, nnz(L) = 4452055
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            2.15E-01 0.000
  1 :   1.23E+01 1.38E-02 0.000 0.0641 0.9900 0.9900  -0.69  1  1  1.4E+00
  2 :   3.45E+00 5.87E-03 0.000 0.4255 0.9000 0.9000   2.14  1  1  3.2E-01
  3 :   1.14E+00 2.61E-03 0.000 0.4457 0.9000 0.9000   4.54  1  1  4.7E-02
  4 :   1.02E+00 9.34E-04 0.000 0.3574 0.9000 0.9000   1.30  1  1  1.6E-02
  5 :   1.00E+00 2.76E-04 0.000 0.2956 0.9000 0.9000   1.03  1  1  4.7E-03
  6 :   9.92E-01 1.46E-05 0.000 0.0530 0.9082 0.9000   1.02  1  1  7.6E-04
  7 :   9.89E-01 4.08E-06 0.000 0.2785 0.9000 0.8622   1.00  1  1  2.1E-04
  8 :   9.89E-01 1.51E-06 0.000 0.3713 0.9000 0.9000   1.00  1  1  7.8E-05
  9 :   9.88E-01 4.68E-07 0.000 0.3090 0.9000 0.9000   1.00  1  1  2.4E-05
 10 :   9.88E-01 1.19E-07 0.000 0.2541 0.9000 0.9000   1.00  1  1  6.1E-06
 11 :   9.88E-01 8.27E-09 0.160 0.0696 0.9904 0.9900   1.00  1  1  5.0E-07
 12 :   9.88E-01 1.32E-09 0.000 0.1590 0.9199 0.9000   1.00  1  1  1.0E-07
 13 :   9.88E-01 5.83E-11 0.246 0.0443 0.9900 0.9900   1.00  1  1  4.7E-09

iter seconds digits       c*x               b*y
 13     82.9   Inf  9.8829189085e-01  9.8829190238e-01
|Ax-b| =   5.0e-09, [Ay-c]_+ =   2.0E-09, |x|=  1.4e+01, |y|=  1.3e+00

Detailed timing (sec)
   Pre          IPM          Post
4.900E-01    8.287E+01    0.000E+00    
Max-norms: ||b||=9.843750e-01, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 50.7171.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.988292
 
Calling sedumi: 4320 variables, 4224 equality constraints
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
Split 1 free variables
eqs m = 4224, order n = 290, dim = 8354, blocks = 3
nnz(A) = 4990 + 0, nnz(ADA) = 9346884, nnz(L) = 4677453
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.04E-01 0.000
  1 :   2.53E-01 3.65E-02 0.000 0.3506 0.9000 0.9000   2.57  1  1  1.4E+00
  2 :   8.76E-01 8.73E-03 0.000 0.2389 0.9000 0.9000   1.70  1  1  2.3E-01
  3 :   9.98E-01 3.01E-04 0.000 0.0345 0.9900 0.9900   1.21  1  1  7.0E-03
  4 :   9.93E-01 8.37E-05 0.000 0.2778 0.9000 0.9000   1.04  1  1  1.9E-03
  5 :   9.91E-01 2.21E-05 0.000 0.2640 0.9000 0.9000   1.01  1  1  5.0E-04
  6 :   9.91E-01 4.64E-06 0.108 0.2101 0.9000 0.0000   1.03  1  1  3.1E-04
  7 :   9.91E-01 9.58E-07 0.000 0.2063 0.9373 0.9000   1.02  1  1  9.0E-05
  8 :   9.89E-01 2.78E-07 0.000 0.2897 0.9000 0.9017   1.02  1  1  2.6E-05
  9 :   9.89E-01 1.15E-07 0.000 0.4157 0.9000 0.9084   1.01  1  1  1.1E-05
 10 :   9.89E-01 6.19E-08 0.000 0.5369 0.9469 0.9000   1.01  1  1  5.5E-06
 11 :   9.89E-01 2.70E-08 0.000 0.4366 0.0000 0.9000   1.01  1  1  2.5E-06
 12 :   9.89E-01 6.99E-09 0.000 0.2586 0.9000 0.8076   1.01  1  1  7.0E-07
 13 :   9.89E-01 2.99E-09 0.000 0.4277 0.7937 0.9000   1.00  1  2  3.0E-07
 14 :   9.89E-01 1.07E-09 0.000 0.3593 0.9000 0.9000   1.00  1  1  1.1E-07
 15 :   9.89E-01 4.24E-10 0.000 0.3949 0.9000 0.9000   1.00  2  2  4.2E-08
 16 :   9.89E-01 1.54E-10 0.000 0.3640 0.9000 0.9000   1.00  2  2  1.5E-08
 17 :   9.89E-01 6.42E-11 0.000 0.4160 0.9000 0.9000   1.00  2  2  6.4E-09

iter seconds digits       c*x               b*y
 17    131.2   Inf  9.8882630019e-01  9.8882630233e-01
|Ax-b| =   4.6e-09, [Ay-c]_+ =   2.9E-09, |x|=  1.4e+01, |y|=  1.4e+00

Detailed timing (sec)
   Pre          IPM          Post
7.100E-01    1.312E+02    1.000E-02    
Max-norms: ||b||=9.843750e-01, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 61.2408.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.988826

Results:
FDLA weights:		 rho = 0.9883 	 tau = 84.9099
FMMC weights:		 rho = 0.9888 	 tau = 88.9949
M-H weights:		 rho = 0.9917 	 tau = 120.2442
MAX_DEG weights:	 rho = 0.9927 	 tau = 136.7523
BEST_CONST weights:	 rho = 0.9921 	 tau = 126.3450
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="cut_grid_example__01.png" alt=""> <img src="cut_grid_example__02.png" alt=""> <img src="cut_grid_example__03.png" alt=""> <img src="cut_grid_example__04.png" alt=""> <img src="cut_grid_example__05.png" alt=""> 
</div>
</div>
</body>
</html>